// analyse regex 

#define NOEXTERN
#include "regex.h"
#include <ctype.h>

static char* analyse_regex(char* pcRegex, struct regex_list_t** pstRegexList);
static char* analyse_squarebracket(char* pcStart, struct regex_list_t* pstRegexList);
static char* analyse_escapechar(char* pcRegex, struct regex_list_t* pstRegexList, char* pcVal);
static char* get_repeatcnt(char* pcCur, int* piMin, int* piMax);
static void set_regexlist(char cMin, char cMax, struct regex_list_t* pstRegexList);
static void negate_regexlist(struct regex_list_t* pstRegexList);

char* get_errorstr()
{
    static char* errorStr[] = {     
        "",
        "Missing } in quantified repetition.",                  // 1
        "Invalid content of repeat range.",
        "Unmatched [ in character class declaration.",
        "Unmatched [^ in character class declaration.",
        "Unmatched [ or [^ in character class declaration.",    // 5
        "Invalid character range.",
        "Escape sequence did not encode a valid character.",
        "Invalid repeat operator.",
        "$ is not at last of regex.",
        "Escape sequence terminated prematurely.",              // 10
        "malloc error.",
        "malloc error.",
        "malloc error.",
        "malloc error.",
        "malloc error.",                                        // 15
        "malloc error.",
        "malloc error.",
        "malloc error.",                                        
        "malloc error.",
        "malloc error.",                                        // 20
        "malloc error.",                                        // 21
        ""
    };

    return errorStr[g_errorno];
} 

static int get_max_referno()
{
    return g_iReferNo;
} 

static int get_next_referno()
{
    return ++g_iReferNo;
} 

// set repeat count
static char* get_repeatcnt(char* pcCur, int* piMin, int* piMax)
{
    char* pcNext = NULL;
    char* pcBraceRight = NULL;
    char* pcComma = NULL;

    pcNext = pcCur + 1;
    switch (*pcNext) 
    {
        // ?
        case QUESTION_MARK:
            *piMin = 0;
            *piMax = 1;

            pcCur++;

            break;
        // +
        case PLUS:
            *piMin = 1;
            *piMax = 0;

            pcCur++;

            break;
        // *
        case STAR:
            *piMin = 0;
            *piMax = 0;

            pcCur++;

            break;
        // {} 
        case BRACE_LEFT:
            pcBraceRight = strchr(pcNext, BRACE_RIGHT);
            if (pcBraceRight == NULL)
            {
                g_errorno = 1;
                g_errorpos = pcNext;
                return NULL;
            } 
            pcComma = strchr(pcNext, COMMA);
            if (pcComma > pcBraceRight)
            {
                pcComma = NULL;
            } 
            if (pcComma == NULL)
            {
                pcComma = pcNext;
            } 
            else
            {
                *pcComma = 0;
            } 
            *pcBraceRight = 0;

            *piMin = atoi(pcNext+1);
            *piMax = atoi(pcComma+1);
            if (*piMax != 0 && *piMax < *piMin)
            {
                g_errorno = 2;
                g_errorpos = pcComma;
                return NULL;
            } 

            if (pcComma != pcNext)
            {
                *pcComma = COMMA;
            } 
            *pcBraceRight = BRACE_RIGHT;

            pcCur = pcBraceRight;
            
            break;
        default:
            *piMin = 1;
            *piMax = 1;

            break;
    } 

    return pcCur;
} 

// Analyse []
static char* analyse_squarebracket(char* pcStart, struct regex_list_t* pstRegexList)
{
    int iI = 0;
    char cTo = 0;
    char cFrom = 0;

    if (*pcStart == 0)
    {
        g_errorno = 3; 
        g_errorpos = pcStart;
        return NULL;
    } 

    if (*pcStart == NEGATED_FLG)
    {
        pstRegexList->stRegex.cNegatedFlg = TRUE;
        pcStart++;
        if (*pcStart == 0)
        {
            g_errorno = 4;
            g_errorpos = pcStart;
            return NULL;
        } 
    } 
    else
    {
        pstRegexList->stRegex.cNegatedFlg = FALSE;
    } 
    
    if (*pcStart != ESCAPE_CHAR)
    {
        cFrom = *pcStart;
        // - ]
        pstRegexList->stRegex.acStr[(unsigned char)(*pcStart++)] = TRUE;
    } 
    else
    {
        pcStart = analyse_escapechar(++pcStart, pstRegexList, &cFrom);
        if (pcStart == NULL)
        {
            return NULL;
        } 
        pcStart ++;
    } 

    while (*pcStart != SQUARE_BRACKET_RIGHT)
    {
        if (*pcStart == 0)
        {
            g_errorno = 5;
            g_errorpos = pcStart;
            return NULL;
        } 

        if (*pcStart == MINOR)
        {
            if (*(pcStart+1) == SQUARE_BRACKET_RIGHT)
            {
                pstRegexList->stRegex.acStr[(unsigned char)(MINOR)] = TRUE;
                pcStart++;
                continue;
            } 

            if (*(pcStart+1) == ESCAPE_CHAR)
            {
                pcStart += 2;
                pcStart = analyse_escapechar(pcStart, pstRegexList, &cTo);
                if (pcStart == NULL)
                {
                    return NULL;
                } 
            } 
            else
            {
                cTo = *(++pcStart);
            } 

            if (cFrom == 0 || cTo == 0 || cFrom > cTo)
            {
                g_errorno = 6;
                g_errorpos = pcStart;
                return NULL;
            } 

            for (iI = cFrom+1; iI <= cTo; iI++)
            {
                pstRegexList->stRegex.acStr[iI] = TRUE;
            } 
            cFrom = cTo = 0;
            pcStart++;
        } 
        else
        {
            if (*pcStart == ESCAPE_CHAR)
            {
                pcStart = analyse_escapechar(++pcStart, pstRegexList, &cFrom);
                if (pcStart == NULL)
                {
                    return NULL;
                } 
                pcStart++;
            } 
            else
            {
                cFrom = *pcStart;
                pstRegexList->stRegex.acStr[(unsigned char)(*pcStart++)] = TRUE;
            } 
        } 
    } 

    if (pstRegexList->stRegex.cNegatedFlg == TRUE)
    {
        for (iI = 1; iI < 256; iI++) 
        {
            pstRegexList->stRegex.acStr[iI] = !pstRegexList->stRegex.acStr[iI];
        } 
    } 

    return pcStart;
} 

static void set_regexlist(char cMin, char cMax, struct regex_list_t* pstRegexList)
{
    char cCh;

    for (cCh = cMin; cCh <= cMax; cCh++)
    {
        pstRegexList->stRegex.acStr[(unsigned char)cCh] = TRUE;
    } 

    return;
} 

static void negate_regexlist(struct regex_list_t* pstRegexList)
{
    int iI;

    for (iI = 1; iI < 256; iI++)
    {
        pstRegexList->stRegex.acStr[iI] = !pstRegexList->stRegex.acStr[iI]; 
    } 
    pstRegexList->stRegex.acStr['\n'] = FALSE;

    return;
} 

static int hex2decimal(char* pcHexStr, int iLen)
{
    int iVal = 0;
    int iI = 0;

    for (iI = 0; iI < iLen; iI++)
    {
        if (pcHexStr[iI] >= '0' && pcHexStr[iI] <= '9')  
        {
            iVal = iVal * 16 + pcHexStr[iI] - '0';
        } 
        else if (pcHexStr[iI] >= 'a' && pcHexStr[iI] <= 'f') 
        {
            iVal = iVal * 16 + pcHexStr[iI] - 'a' + 10;
        } 
        else if (pcHexStr[iI] >= 'A' && pcHexStr[iI] <= 'F') 
        {
            iVal = iVal * 16 + pcHexStr[iI] - 'A' + 10;
        } 
        else
        {
            g_errorno = 7;
            g_errorpos = pcHexStr+iI;
            iVal = -1;
            break;
        } 
    } 

    return iVal;
} 

static int oct2decimal(char* pcOctStr, int iLen, int* piOctCnt)
{
    int iVal = 0;
    int iI = 0;

    if (pcOctStr[0] >= '0' && pcOctStr[0] <= '3')
    {
        iLen = 3;
    } 
    else
    {
        iLen = 2;
    } 

    for (iI = 0; iI < iLen; iI++)
    {
        if (pcOctStr[iI] >= '0' && pcOctStr[iI] <= '7')  
        {
            iVal = iVal * 8 + pcOctStr[iI] - '0';
        } 
        else
        {
            break;
        } 
    } 

    *piOctCnt = iI;

    return iVal;
} 

static char* analyse_escapechar(char* pcRegex, struct regex_list_t* pstRegexList, char* pcVal)
{
    char* pcCur;
    int iVal = 0;
    int iOctCnt = 0;

    pcCur = pcRegex;
    switch (*pcCur)
    {
        case 'd':
            set_regexlist('0', '9', pstRegexList);
            if (pcVal != NULL) 
                *pcVal = 0;
            break;

        case 'D':
            set_regexlist('0', '9', pstRegexList);
            negate_regexlist(pstRegexList);
            if (pcVal != NULL) 
                *pcVal = 0;
            break;

        case 'w':
            set_regexlist('0', '9', pstRegexList);
            set_regexlist('a', 'z', pstRegexList);
            set_regexlist('A', 'Z', pstRegexList);
            set_regexlist('_', '_', pstRegexList);
            if (pcVal != NULL) 
                *pcVal = 0;
            break;

        case 'W':
            set_regexlist('0', '9', pstRegexList);
            set_regexlist('a', 'z', pstRegexList);
            set_regexlist('A', 'Z', pstRegexList);
            set_regexlist('_', '_', pstRegexList);
            negate_regexlist(pstRegexList);
            if (pcVal != NULL) 
                *pcVal = 0;
            break;

        case 's':
            set_regexlist(' ', ' ', pstRegexList);
            set_regexlist('\f', '\f', pstRegexList);
            set_regexlist('\t', '\t', pstRegexList);
            set_regexlist('\v', '\v', pstRegexList);

            if (pcVal != NULL) 
                *pcVal = 0;
            break;

        case 'S':
            set_regexlist(' ', ' ', pstRegexList);
            set_regexlist('\f', '\f', pstRegexList);
            set_regexlist('\t', '\t', pstRegexList);
            set_regexlist('\v', '\v', pstRegexList);
            negate_regexlist(pstRegexList);

            if (pcVal != NULL) 
                *pcVal = 0;
            break;

        case 't':
            set_regexlist('\t', '\t', pstRegexList);
            if (pcVal != NULL) 
                *pcVal = '\t';
            break;

        case 'v':
            set_regexlist('\v', '\v', pstRegexList);
            if (pcVal != NULL) 
                *pcVal = '\v';
            break;

        case 'f':
            set_regexlist('\f', '\f', pstRegexList);
            if (pcVal != NULL) 
                *pcVal = '\f';
            break;

        case 'r':
            set_regexlist('\r', '\r', pstRegexList);
            if (pcVal != NULL) 
                *pcVal = '\r';
            break;

        case 'n':
            set_regexlist('\n', '\n', pstRegexList);
            if (pcVal != NULL) 
                *pcVal = '\n';
            break;

        // Hex
        case 'x':
        case 'X':
            iVal = hex2decimal(pcCur+1, 2);
            if (iVal < 0)
            {
                return NULL;
            } 
            set_regexlist(iVal, iVal, pstRegexList);
            pcCur += 2;
            if (pcVal != NULL) 
                *pcVal = (char)iVal;

            break;

        // Octonary
        case '0':
        case '1':
        case '2':
        case '3':
        case '4':
        case '5':
        case '6':
        case '7':
            iVal = oct2decimal(pcCur, 3, &iOctCnt);
            set_regexlist(iVal, iVal, pstRegexList);
            pcCur += iOctCnt - 1;
            if (pcVal != NULL) 
                *pcVal = (char)iVal;
            break;

        case '*':
        case '+':
        case '?':
        default:
            set_regexlist(*pcCur, *pcCur, pstRegexList);
            if (pcVal != NULL) 
                *pcVal = *pcCur;
            break;
    } 

    return pcCur;
} 

static int is_referno(char* pcRegex)
{
    char* pcNext;

    pcNext = pcRegex + 1;
    if (isdigit(*pcNext) && ((*pcNext-'0') <= get_max_referno()) && *pcNext != '0')
    {
        return TRUE;
    } 

    return FALSE;
} 

static struct regex_list_t* reverse_regexlist(struct regex_list_t* pstRegexList)
{
    struct regex_list_t* pstCur = NULL;
    struct regex_list_t* pstNext = NULL;
    struct regex_list_t* pstPrev = NULL;

    for (pstNext = pstRegexList; pstNext != NULL;)
    {
        pstCur = pstNext;
        pstNext = pstNext->pstNext;
        
        pstCur->pstNext = pstPrev;
        pstPrev = pstCur;
    } 

    return pstPrev;
} 

static char* analyse_regex(char* pcRegex, struct regex_list_t** ppstRegexList)
{
	char* pcCur;
	char* pcNext;
    struct regex_list_t* pstRegexList = NULL;
    struct regex_list_t* pstCur = NULL;

    pcCur = pcRegex;
	while (*pcCur)
	{
		switch (*pcCur)
		{
			case STAR:
			case PLUS:
            case QUESTION_MARK:
                g_errorno = 8;
                g_errorpos = pcCur;
				return NULL;

            // []
			case SQUARE_BRACKET_LEFT:
				pcCur++;

                pstRegexList = malloc(sizeof(struct regex_list_t));
                if (pstRegexList == NULL)
                {
                    g_errorno = 11;
                    return NULL;
                } 
                memset(pstRegexList, 0, sizeof(struct regex_list_t));

                pcCur = analyse_squarebracket(pcCur, pstRegexList);
                if (pcCur == NULL)
                {
                    return NULL;
                } 
                pcCur = get_repeatcnt(pcCur, &pstRegexList->stRegex.iMin, &pstRegexList->stRegex.iMax);

                pstRegexList->pstNext = pstCur;
                pstCur = pstRegexList;

				break;
            // $ 
			case MATCH_END:
				pcNext = pcCur + 1;
				if (*pcNext != 0 && strcmp(pcNext, ")") != 0)
				{
                    g_errorno = 9;
                    g_errorpos = pcNext;
					return NULL;
				} 
				else
				{
                    pstRegexList = malloc(sizeof(struct regex_list_t));
                    if (pstRegexList == NULL)
                    {
                        g_errorno = 12;
                        return NULL;
                    } 
                    memset(pstRegexList, 0, sizeof(struct regex_list_t));

                    // $ match '\0' '\n'
					pstRegexList->stRegex.acStr[0] = 1;
                    pstRegexList->stRegex.acStr['\n'] = 0;

                    pstRegexList->stRegex.cNegatedFlg = FALSE;
                    pstRegexList->stRegex.iMin = 1;
                    pstRegexList->stRegex.iMax = 1;

                    pstRegexList->pstNext = pstCur;
                    pstCur = pstRegexList;
				} 
				
				break;
            case BRACKET_LEFT:
            case BRACKET_RIGHT:
            case OP_OR:
                *ppstRegexList = reverse_regexlist(pstCur);
                return pcCur;

            // \d, \s \D \S etc.
            case ESCAPE_CHAR:
                if (is_referno(pcCur) == TRUE)
                {
                    *ppstRegexList = reverse_regexlist(pstCur);
                    return pcCur;
                } 

                pcCur++;
                if (*pcCur == 0)
                {
                    g_errorno = 10;
                    g_errorpos = pcCur;
                    return NULL;
                } 

                pstRegexList = malloc(sizeof(struct regex_list_t));
                if (pstRegexList == NULL)
                {
                    g_errorno = 13;
                    return NULL;
                } 
                memset(pstRegexList, 0, sizeof(struct regex_list_t));

                pcCur = analyse_escapechar(pcCur, pstRegexList, NULL);
                if (pcCur == NULL)
                {
                    return NULL;
                } 

                pcCur = get_repeatcnt(pcCur, &pstRegexList->stRegex.iMin, &pstRegexList->stRegex.iMax);
                if (pcCur == NULL)
                {
                    return NULL;
                } 

                pstRegexList->pstNext = pstCur;
                pstCur = pstRegexList;
                
                break;
			default:
                pstRegexList = malloc(sizeof(struct regex_list_t));
                if (pstRegexList == NULL)
                {
                    g_errorno = 14;
                    return NULL;
                } 
                memset(pstRegexList, 0, sizeof(struct regex_list_t));

                // .
                if (*pcCur == ANY_CHAR)
                {
                    memset(pstRegexList->stRegex.acStr+1, 1, 255);
                    // . not match \n
                    pstRegexList->stRegex.acStr['\n'] = 0;
                } 
                else
                {
                    pstRegexList->stRegex.acStr[(unsigned char)(*pcCur)] = 1;
                } 

                pcCur = get_repeatcnt(pcCur, &pstRegexList->stRegex.iMin, &pstRegexList->stRegex.iMax);
                if (pcCur == NULL)
                {
                    return NULL;
                } 
                pstRegexList->stRegex.cNegatedFlg = FALSE;

                pstRegexList->pstNext = pstCur;
                pstCur = pstRegexList;

				break;
		} 

		pcCur++;
	} 

    *ppstRegexList = reverse_regexlist(pstCur);
	return pcCur;
} 

// analyse regex
char* analyse_all(char* pcRegex, struct regex_group_t** ppstRegex)
{
    struct regex_group_t* pstRegex = NULL;
    struct regex_group_t* pstRootRegex = NULL;
    struct regex_group_t* pstFirstRegex = NULL;
    struct regex_group_t* pstCurRegex = NULL;
    struct regex_group_t* pstNewRegex = NULL;
    struct regex_group_t* pstNewRegex_prev = NULL;
    char* pcCur = NULL;
    int iReferNo = 0;

    if (pcRegex == NULL)
    {
        g_errorno = 11;
        return NULL;
    } 

    pstRootRegex = malloc(sizeof(*pstRootRegex));
    if (pstRootRegex == NULL)
    {
        g_errorno = 15;
        return NULL;
    } 
    memset(pstRootRegex, 0, sizeof(*pstRootRegex));

    // skip (
	pcCur = pcRegex + 1;
    iReferNo = get_next_referno();

    while (*pcCur != BRACKET_RIGHT)
    {
        pstRegex = NULL;
        switch (*pcCur)
        {
            case BRACKET_LEFT:
                pcCur = analyse_all(pcCur, &pstRegex);
                if (pcCur == NULL)
                {
                    return NULL;
                } 

                break;
            // max 9 (\1-\9)
            case ESCAPE_CHAR:
                if (!isdigit(*(pcCur+1)) || (*(pcCur+1) - '0') > get_max_referno())
                {
                    // no break
                } 
                else
                {
                    pstRegex = malloc(sizeof(*pstRegex));
                    if (pstRegex == NULL)
                    {
                        g_errorno = 16;
                        return NULL;
                    } 
                    memset(pstRegex, 0, sizeof(*pstRegex));
                    pcCur++;
                    pstRegex->iReferBackNo = *pcCur - '0';
                    pstRegex->iMin = pstRegex->iMax = 1;

                    pcCur++;
                     
                    break;
                } 
            default:
                pstRegex = malloc(sizeof(*pstRegex));
                if (pstRegex == NULL)
                {
                    g_errorno = 17;
                    return NULL;
                } 
                memset(pstRegex, 0, sizeof(*pstRegex));
                pcCur = analyse_regex(pcCur, &pstRegex->pstRegList);
                pstRegex->iMin = pstRegex->iMax = 1;

                if (pcCur == NULL)
                {
                    return NULL;
                } 

                break;
        } 
        // | grouping 
        // etc. aaa|(bbb)+(ccc)*|ddd --> (aaa)|((bbb)+(ccc)*)|(ddd)
        if (*pcCur == OP_OR)
        {
            pstNewRegex = malloc(sizeof(*pstRegex));
            if (pstNewRegex == NULL)
            {
                g_errorno = 18;
                return NULL;
            } 
            memset(pstNewRegex, 0, sizeof(*pstNewRegex));

            pstNewRegex->cOr = TRUE;
            pstNewRegex->iMin = 1;
            pstNewRegex->iMax = 1;
            pcCur++;
        } 
        else
        {
            pstNewRegex = NULL;
        } 

        if (pstRegex != NULL)
        {
            if (pstFirstRegex == NULL) 
            {
                if (pstNewRegex == NULL)
                {
                    pstFirstRegex = pstCurRegex = pstRegex;
                } 
                else
                {
                    pstNewRegex->pstChild = pstRegex;
                    pstCurRegex = pstNewRegex;

                    pstFirstRegex = pstNewRegex;
                } 
                pstNewRegex_prev = pstFirstRegex;
            } 
            else
            {
                pstCurRegex->pstBrother = pstRegex;
                pstCurRegex = pstRegex;

                if (pstNewRegex != NULL)
                {
                    pstNewRegex->pstChild = pstNewRegex_prev->pstBrother;
                    pstNewRegex_prev->pstBrother = pstNewRegex;
                    pstNewRegex_prev = pstNewRegex;

                    pstCurRegex = pstNewRegex;
                } 
            } 
        } 
    } 

    pstFirstRegex->iReferNo = iReferNo;

    pstRootRegex->pstChild = pstFirstRegex;
    // * + ? {n,m} 
    pcCur = get_repeatcnt(pcCur, &pstRootRegex->iMin, &pstRootRegex->iMax);
    if (pcCur == NULL)
    {
        return NULL;
    } 
    pcCur++;

    *ppstRegex = pstRootRegex;
    return pcCur;
} 

